home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / LOGMIN_D.C < prev    next >
C/C++ Source or Header  |  1992-03-12  |  12KB  |  344 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : LOGMIN_D.C
  4.  *
  5.  *    Written By : Eng-Huat Ong and Kian-Mong Low.
  6.  *
  7.  *      This is the actual minimization algorithm. Variation from the actual
  8.  *    LOGMIN algorithm is as follows:
  9.  *        1.    Minterms with adjacency 0 or 1 is minimised first
  10.  *        2.    Select next minterm with lowest adjacency wrt b-array
  11.  *        3.    To shrink the CPT, select an adjacent term, mi that has the
  12.  *            largest wi AND is already covered
  13.  *
  14.  * --------------------------------------------------------------------------
  15.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  16.  *    University.
  17.  *
  18.  *    You are free to use, copy and distribute this software and its
  19.  *    documentation providing that:
  20.  *
  21.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  22.  *
  23.  *        IT IS NOT MODIFIED IN ANY WAY.
  24.  *
  25.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  26.  *
  27.  *    This program is provided "AS IS" without any warranty, expressed or
  28.  *    implied, including but not limited to fitness for any particular
  29.  *    purpose.
  30.  *
  31.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  32.  *    appreciated. Please send to:
  33.  *
  34.  *        Boon-Tiong Tan or Othman Bin Ahmad
  35.  *        School of EEE
  36.  *        Nanyang Technological University
  37.  *        Nanyang Avenue
  38.  *        Singapore 2263
  39.  *        Republic of Singapore
  40.  *
  41.  ***************************************************************************/
  42.  
  43. #include <stdio.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46. #define mask8 255
  47.  
  48. unsigned char   *logmin_d(a, b)              /* pointer to a & b array passed */
  49. unsigned char   *a, *b;
  50.  
  51. {
  52.    unsigned short   pterm, ma, mb, *pm, pos;
  53.    unsigned  long   m, topow();
  54.    register  long   i, wo, wi;
  55.    register  char   j;
  56.          char   test;
  57.    unsigned  char   *c, *d, *e, *s, *temp, count, adj0, adji;
  58.    unsigned  char   n, adj, adjacency(), nspm, cover;
  59.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  60.  
  61.  
  62.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  63.  
  64.    n    = *a;                          /* no. of variables */
  65.    nspm = *(a+3);                      /* no. of bytes/minterm */
  66.    ma = *(a+2)<<8 | *(a+1);            /* no. of minterms in a-array */
  67.  
  68.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  69.    if (temp == 0)
  70.       {
  71.      printf("Out of memory -- LOGMIN_D, *temp\n");
  72.      printf("Program terminated - 1\n");
  73.      exit(0);
  74.       }
  75.  
  76.    s = (unsigned char *) malloc(4);                /* header of s-array */
  77.    if (s == 0)
  78.       {
  79.      printf("Out of memory -- LOGMIN_D, *s\n");
  80.      printf("Program terminated - 2\n");
  81.      exit(0);
  82.       }
  83.  
  84.    pterm = 0;                                /* no. of product term */
  85.  
  86.    /***
  87.     ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  88.     ***/
  89.  
  90.    for (i=0; i<mb; i++)                      /* for adj = 0 or 1 */
  91.       {
  92.      *b = n;                             /* assign back to n */
  93.  
  94.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  95.      c = adjacent(temp, a, 1);           /* obtain the adjacent terms */
  96.      adj = *(c+1);                       /* adjacency of minterm */
  97.  
  98.      if (adj <= 1)                       /* adjacency 0 or 1 */
  99.         {
  100.            d = cpt(c);                   /* generate CPT */
  101.  
  102.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  103.            if (s == 0)
  104.           {
  105.              printf("Out of memory -- LOGMIN_D, *s\n");
  106.              printf("Program terminated - 3\n");
  107.              exit(0);
  108.           }
  109.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  110.            pterm++;                      /* product term count */
  111.  
  112.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  113.            i = (char) *b;                /* index pointer of b-array */
  114.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  115.  
  116.            free(d);                    /* free pointer */
  117.         }
  118.      free(c);                            /* free pointer */
  119.       }
  120.  
  121.     /***
  122.      ***  MINIMIZE MINTERMS WITH ADJACENCY GREATER THAN 1
  123.      ***/
  124.  
  125.     while (mb > 0)
  126.        {
  127.       adj0 = 255;                     /* max for 8-bit */
  128.  
  129.       *b = n;                         /* assign back to n */
  130.  
  131.       /***
  132.        ***  SELECT 1ST MINTERM WITH LOWEST ADJACENCY WRT B-ARRAY
  133.        ***/
  134.  
  135.       for (i=0; i<mb; i++)
  136.          {
  137.         memcpy(temp, (b+4+nspm*i), nspm);    /* pick a minterm */
  138.         adji = adjacency(temp, b);           /* obtain adjacency */
  139.  
  140.         if (adji<adj0)                       /* look for lowest adj */
  141.            {
  142.               adj0 = adji;
  143.               pos = i;                       /* position of minterm */
  144.            }
  145.           }
  146.        memcpy(temp, (b+4+nspm*pos), nspm);       /* pick the required minterm */
  147.  
  148.        /***
  149.         ***  GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
  150.         ***/
  151.  
  152.        c = adjacent(temp, a, 255);          /* obtain adjacent terms */
  153.        adj = *(c+1);                        /* adjacency of minterms */
  154.        d = cpt(c);                          /* generate CPT */
  155.        e = ssm(d);                          /* generate SSM */
  156.        m = topow(*(e+1));                   /* no. of SSM terms */
  157.  
  158.        for (j=0; j<m; j++)                  /* check for SSM coverage */
  159.           {
  160.          memcpy (temp, (e+4+nspm*j), nspm);   /* pick SSM term */
  161.          test = exist (temp, a, ma);
  162.          if (test == -1)                /* SSM term not in a-array */
  163.              break;
  164.           }
  165.  
  166.        /***
  167.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  168.         ***/
  169.  
  170.        if (test == 0)                       /* all SSM's covered by fn */
  171.           {
  172.          if (m > 65536)                  /* too many SSM terms */
  173.             {
  174.                printf("Product Term Too Huge \n");
  175.                printf("Program terminated \n");
  176.                exit(0);
  177.             }
  178.          *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  179.          *(e+2) = (m-1)>>8 & mask8;
  180.          b = reduce(e,b,i);             /* remove minterms covered from b-array */
  181.          mb = *(b+2)<<8 | *(b+1);       /* no. of minterms in b-array */
  182.  
  183.          s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  184.          if (s == 0)
  185.             {
  186.                printf("Out of memory -- LOGMIN_D, *s\n");
  187.                printf("Program terminated - 4\n");
  188.                exit(0);
  189.             }
  190.          memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  191.          pterm++;                       /* no. of product terms */
  192.  
  193.          free(d);                       /* free pointers */
  194.          free(e);
  195.           }
  196.        else
  197.           {
  198.          /***
  199.           ***  SSM NOT COVERED BY THE FUNCTION
  200.           ***/
  201.  
  202.          free(d);                       /* free pointer */
  203.          cover =0;                      /* coverage status */
  204.  
  205.          while (!cover)        /* do until shrinked SSM is covered */
  206.             {
  207.                /***
  208.             ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
  209.             ***/
  210.  
  211.                wo = -1;                        /* initial value */
  212.                for (j=0; j<adj; j++)           /* do for all adjacent terms */
  213.               {
  214.                  memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
  215.  
  216.                  wi = adj_of_mi(temp,e,a);           /* obtain wi */
  217.                  if (wi>wo)
  218.                 {
  219.                    if (wo != -1)                 /* not the first */
  220.                       free(pm);
  221.                    wo = wi;                      /* new lowest value */
  222.                    count = 1;                    /* reset count to 1 */
  223.  
  224.                    pm = (unsigned short *) malloc(2);  /* space for pm */
  225.                    if (pm==0)
  226.                       {
  227.                      printf("Out of memory -- LOGMIN_D, *pm\n");
  228.                      printf("Program terminated - 5\n");
  229.                      exit(0);
  230.                       }
  231.                    *pm = j;                      /* first element */
  232.                 }
  233.                  else if (wi==wo)                    /* wi as large */
  234.                 {
  235.                    count++;                      /* no. of element in pm-array */
  236.  
  237.                    pm = (unsigned short *) realloc (pm, 2*count);  /* more space */
  238.                    if (pm==0)
  239.                       {
  240.                      printf("Out of memory -- LOGMIN_D, *pm\n");
  241.                      printf("Program terminated - 6\n");
  242.                      exit(0);
  243.                       }
  244.                    *(pm+count-1) = j;            /* elements of pm-array */
  245.                 }
  246.               }
  247.                free(e);
  248.  
  249.                /***
  250.             ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  251.             ***/
  252.  
  253.                for (j=0; j<count; j++)              /* do for all element in pm-array */
  254.               {
  255.                  memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);    /* pick adj term */
  256.                  test = exist(temp,b,mb);
  257.                  if (test == -1)                               /* already covered */
  258.                 break;
  259.               }
  260.  
  261.                if (j==count)                     /* select the 1st if all not covered */
  262.               j = 0;
  263.  
  264.                adj--;                            /* no. of adj terms in c-array */
  265.                *(c+1) = adj;                     /* adjacency after shrinking CPT */
  266.                pos = *(pm+j);                    /* required position of adj term */
  267.  
  268.                free(pm);                         /* free pointer */
  269.  
  270.                /***
  271.             ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT, SSM
  272.             ***  AND TEST FOR COVERAGE BY FUNCTION
  273.             ***/
  274.  
  275.                memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink CPT */
  276.  
  277.                c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* reduce space */
  278.                if (c==0)
  279.               {
  280.                  printf("Out of memory -- LOGMIN_D, *c\n");
  281.                  printf("Program terminated - 7\n");
  282.                  exit(0);
  283.               }
  284.  
  285.                d = cpt(c);                  /* generate CPT */
  286.                e = ssm(d);                  /* generate SSM */
  287.                m = topow(*(e+1));           /* no. of SSM terms */
  288.  
  289.                for (i=0; i<m; i++)          /* check SSM coverage by function */
  290.               {
  291.                  memcpy(temp, (e+4+nspm*i), nspm);  /* pick SSM term */
  292.                  test = exist(temp,a,ma);
  293.                  if (test == -1)                    /* SSM term not covered */
  294.                 break;
  295.               }
  296.  
  297.                /***
  298.             ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
  299.             ***  AND SELECT SHRINKED CPT AS PRODUCT TERM
  300.             ***/
  301.  
  302.                if (test==0)                   /* SSM covered */
  303.               {
  304.                  if (m > 65536)                  /* too many SSM terms */
  305.                 {
  306.                    printf("Product Term Too Huge \n");
  307.                    printf("Program terminated \n");
  308.                    exit(0);
  309.                 }
  310.                  *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  311.                  *(e+2) = (m-1)>>8 & mask8;
  312.                  b = reduce(e, b, i);     /* remove minterms covered from b-array */
  313.                  mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
  314.  
  315.                  s = (unsigned char *) realloc(s, 4+n*(pterm+1));  /* more space */
  316.                  if (s==0)
  317.                 {
  318.                    printf("Out of memory -- LOGMIN_D, *s\n");
  319.                    printf("Program terminated - 8\n");
  320.                    exit(0);
  321.                 }
  322.                  memcpy ((s+4+n*pterm), d, n);      /* add shrinked CPT to soln array */
  323.                  pterm++;                           /* no. of product terms */
  324.  
  325.                  cover = 1;                         /* coverage status */
  326.                  free(e);                           /* free pointer */
  327.               }
  328.                free (d);                      /* free pointer */
  329.             }
  330.           }
  331.       free(c);                   /* free pointer */
  332.       }
  333.    *s = n;                           /* no. of variables */
  334.    *(s+1) = pterm & mask8;           /* no. of product terms in 2 bytes */
  335.    *(s+2) = pterm>>8 & mask8;
  336.  
  337.    free(temp);                       /* free pointer */
  338.    free(a);
  339.    free(b);
  340.  
  341.    return(s);                        /* return solution array */
  342. }
  343.  
  344.